package com.tucc.hello.leetcode.no401_800.no525;

import cn.hutool.json.JSONUtil;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1};
//        int[] nums = {1, 0, 1, 0, 1, 1};
//        int[] nums = {0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1};
//        int[] nums = {1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0};
//        int[] nums = {1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1};
//        nums = JSONUtil.toList(TEST_DATA, Integer.class).stream().mapToInt(o -> o).toArray();
//        nums = new int[]{  0,   1,   1,   0,   0,   0,   0,   1,   0,   1,   0,   1,   1,   0,   0,   0,   0,   1,   1,   1,   0,   0,   1,   1,   1,   0,   1,   1,   0,   1,   1};
//        nums = new int[]{  0,   1,   1,   0,   0,   0,   0,   1,   0,   1,   0,   1,   1,   0,   0,   0,   0,   1,   1,   1,   0,   0};
//        nums = new int[]{0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1};
        //        System.out.println(solution.findMaxLength2(nums));
        System.out.println(solution.findMaxLength2(nums));

    }

    /**
     * 动态规划
     * @param nums
     * @return
     */
    public int findMaxLength(int[] nums) {
        if (nums.length < 1) {
            return 0;
        }
        int max = 0;
        //dp[n] = 0-n范围内n结尾 符合条件的子数组的最大长度
        int[] dp = new int[nums.length];
        dp[0] = 0;
        //dp2[n] = m  nums[m]=nums[n] 以和当前元素相同的元素结尾的符合条件的子数组的最小终止下标
        //目的为 如果要丢弃nums[n]， 定位到下一个丢弃比nums[n]数量多一个的1-nums[n]的 下标
        // 举例 如果nums[m]为0, 则定位到m, nums[m]也为0， 则[n,m)之间 1的个数会比0多一个
        // 保证 m是最小的符合条件的值
        int[] dp2 = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            // 如果 num[i] = 1, num[i - 1] = 0, 则 当前长度为 0-(i-2)之间 以i-2结尾的子数组的长度 + 2，即dp[i - 2]
            if (1 - nums[i] == nums[i - 1]) {
                dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
            } else {
                // 考虑 i-1结尾的子数组的前一个元素， 下标当前i- （i-1）结尾的子数组的长度 再减 1
                //                                            即dp[i - 1]
                int tempIndex = i - dp[i - 1];
                // 考虑长度增加的情况， 可以连接的情况
                // 如果存在 这样的前一个元素 且 这个值与当前值相反
                if (tempIndex > 0 && (1 - nums[i] == nums[tempIndex - 1])) {
                    // 则至少长度就是 i - tempIndex + 2 , i - tempIndex = dp[i -1]
                    // 但还要考虑能否 和再前一个元素组成的数组相连
                    dp[i] = dp[i - 1] + 2 + (tempIndex - 2 > 0 ? dp[tempIndex - 2] : 0);
                    // 以下是为了设置dp2
                    if (nums[i] == nums[tempIndex - 1]) {
                        if (dp2[tempIndex - 1] == 0) {
                            dp2[tempIndex - 1] = i;
                        } else {
                            dp2[tempIndex - 1] = Math.min(i, dp2[tempIndex - 1]);
                        }
                    }
                } else {
                    // 没有符合条件的前一个元素， 则考虑长度缩减的情况
                    // 如果num[i-1]的数组的第一个值 和当前值一样， 则相当于平移一个距离， 舍弃tempIndex, 加入i，长度不变
                    if (nums[i] == nums[tempIndex]) {
                        dp[i] = dp[i - 1];
                    } else {
                        // 否则 查看丢弃 tempIndex之后下一个可以定位的值
                        // 举例， 如当前值 为1， 则tempIndex的值为 0， dp2[tempIndex]即 丢弃 k个1，k-1个0且nums[dp[tempIndex]]=0
                        int temp2 = dp2[tempIndex];
                        if (temp2 != 0) {
                            // 考虑从当前丢弃的值开始 即 i - temp2 + 1
                            // 但还要考虑 能否再和前一个元素相连的情况
                            dp[i] = i - temp2 + 1 + (temp2 > 0 ? dp[temp2 - 1] : 0);
                        }
                    }
                }
            }
            // 以下是也为了设置dp2
            if (dp[i] > 0) {
                int start = i - dp[i] + 1;
                if (nums[i] == nums[start]) {
                    if (dp2[start] > i || dp2[start] == 0) {
                        dp2[start] = i;
                    }
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }

    /**
     * 前缀和
     * @param nums
     * @return
     */
    public int findMaxLength2(int[] nums) {
        int maxLength = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int counter = 0;
        map.put(counter, -1);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num == 1) {
                counter++;
            } else {
                counter--;
            }
            if (map.containsKey(counter)) {
                int prevIndex = map.get(counter);
                maxLength = Math.max(maxLength, i - prevIndex);
            } else {
                map.put(counter, i);
            }
        }
        return maxLength;
    }


    private void anlysis(int[] dp, int nums[], int[] dp2) {

        printArr(nums);

        for (int i = 0; i < nums.length; i++) {
            System.out.print(String.format("%3d", i));
            if (i != nums.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println();
        printArr(dp);

        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            int a = 0;
            int b = 0;
            int c = 0;
            for (int j = i; j >= 0; j--) {
                if (nums[j] == 1) {
                    a++;
                } else {
                    b++;
                }
                if (a == b) {
                    c = a;
                }
            }
            System.out.print(String.format("%3d", c * 2));
            max = Math.max(max, c * 2);
            if (i != nums.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println();
        System.out.println();
        System.out.println(max);
        System.out.println();

        printArr(dp2);
    }

    private void printArr(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.print(String.format("%3d", nums[i]));
            if (i != nums.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println();
    }


    public static String TEST_DATA = "[0,1,1,0,0,0,0,1,0,1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,0,1,0,0,1,1,0,1,0,0,1,1,0,0,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1,1,0,1,1,0,1,1,1,1,0,1,0,0,1,0,0,1,1,0,1,1,0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,1,1,1,0,0,0,1,1,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,0,0,0,0,1,1,1,0,0,1,1,1,1,1,0,1,1,0,0,1,0,1,1,0,0,1,0,1,1,1,1,0,0,0,0,0,1,1,0,1,1,1,1,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,0,1,0,1,1,1,0,1,1,0,1,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,1,1,0,1,1,1,0,1,1,0,1,1,0,1,1,0,1,0,0,0,0,1,1,0,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,1,0,1,0,1,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,1,1,0,1,0,0,1,0,1,0,0,1,1,1,0,1,1,1,1,0,0,1,0,1,1,1,1,0,1,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,1,1,0,0,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,0,0,0,0,0,1,0,1,1,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,0,1,1,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,0,0,0,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,1,1,0,1,0,0,0,1,0,1,1,1,1,1,0,1,1,0,0,0,1,1,1,1,0,0,0,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,1,1,1,0,1,0,0,1,0,0,0,0,1,1,1,0,1,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,1,0,1,0,1,1,1,1,0,0,1,0,1,1,1,1,0,0,0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,0,1,1,0,1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,1,1,1,1,0,1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,0,0,0,1,1,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,1,0,0,0,1,1,1,1,0,1,1,0,1,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,1,0,1,1,1,1,0,0,0,1,0,1,0,0,1,0,0,0,1]";
}
